package z_exam;

import java.util.Arrays;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/18 16:18
 */
public class test3 {

    public static void main(String[] args) {
        int[] arr = {1332802,1177178,1514891,871248,753214,123866,1615405,
                328656,1540395,968891,1884022,252932,1034406,1455178,821713,
                486232,860175,1896237,852300,566715,1285209,1845742,883142,
                259266,520911,1844960,218188,1528217,332380,261485,1111670,16920,
                1249664,1199799,1959818,1546744,1904944,51047,1176397,190970,
                48715,349690,673887,1648782,1010556,1165786,937247,986578,798663};
        int kth = findKth(arr, 49, 24);
        Arrays.sort(arr);
        System.out.println(kth);
        String string = Arrays.toString(arr);
        System.out.println(string);
        System.out.println(arr[arr.length-24]);
    }

    public static int findKth(int[] a, int n, int K) {
        // write code here
        quickSort(a, 0, n - 1, K);
        return a[K - 1];
    }

    public static void quickSort(int[] arr, int i, int j, int K){
        if(i < j){
            //返回索引 [0, p - 1] p [p + 1, n]
            int p = partition(arr, i, j);
            if(p + 1 == K){
                return;
            }else if(p + 1 < K){
                //p + 1 < k
                quickSort(arr, p + 1, j, K);
            }else{
                //p + 1 > k
                quickSort(arr, i, p - 1, K);
            }
        }
    }

    public static int partition(int[] arr, int i, int j){
        int temp = arr[i];
        while(i < j){
            while(i < j && arr[j] <= temp){
                j--;
            }
            arr[i] = arr[j];
            while(i < j && arr[i] >= temp){
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;
        return i;
    }



}
